/*
 * list.h
 *
 *  Created on: Jun 10, 2011
 *      Author: Gilad & Yotam
 */

#ifndef LIST_H_
#define LIST_H_

#include "mtm.h"
#include <iostream>

using namespace ListExceptions;

template<typename T> struct Node;
template<typename T> class Iterator;
template<typename T> class List;

/* -============================- Node type -============================- */

template<typename T>
struct Node {
	T *data;
	Node<T> *next;

	Node(); //creates a dummy node (both fields point to NULL)
	Node(const T& input); //creates a node with NULL as next and points to data
	~Node();
};

template<typename T>
Node<T>::Node() :
	data(NULL), next(NULL) {
}
template<typename T>
Node<T>::Node(const T& input) :
	data(new T(input)), next(NULL) {
}
template<typename T>
Node<T>::~Node() {
	delete data;
}

/* -==========================- List iterator -==========================- */

template<typename T>
class Iterator {
	List<T>* motherList;
	Node<T>* current;
public:
	Iterator(List<T>* list, Node<T>* node);
	Iterator& operator=(const Iterator& second);
	Iterator& operator++();
	Iterator operator++(int);
	T& operator*();
	bool operator==(const Iterator& iterator);
	bool operator!=(const Iterator& iterator);
	friend void List<T>::insert(const T& data, Iterator<T> iterator);
	friend void List<T>::remove(Iterator<T> iterator);
};

template<typename T>
Iterator<T>::Iterator(List<T>* list, Node<T>* node) :
	motherList(list), current(node) {
}
template<typename T>
Iterator<T>& Iterator<T>::operator=(const Iterator& second) {
	current = second.current;
	motherList = second.motherList;
	return *this;
}
template<typename T>
Iterator<T>& Iterator<T>::operator++() {
	// if not in the end already (pointing at the dummy) - advance
	if (current->next != NULL) {
		current = current->next;
	}
	return *this;
}
template<typename T>
Iterator<T> Iterator<T>::operator++(int) {
	Iterator<T> tempIterator = *this;
	if (current->next != NULL) {
		current = current->next;
	}
	return tempIterator;
}
template<typename T>
T& Iterator<T>::operator*() {
	//check if at the dummy node...
	if (current->next == NULL) {
		throw ElementNotFound();
	}
	return *(current->data);
}
template<typename T>
bool Iterator<T>::operator==(const Iterator& iterator) {
	return ((current == iterator.current)
			&& (motherList == iterator.motherList));
}
template<typename T>
bool Iterator<T>::operator!=(const Iterator& iterator) {
	return (!this->operator==(iterator));
}

/* -==========================- Generic list -==========================- */
template<typename T>
class List {
	int size;
	Node<T>* head;
	//checks if two list pointers are pointing to the same list
	void compareLists(const List* list2) {
		if (this != list2) {
			throw ElementNotFound();
		}
	}
/*
 * findMix - this function finds the min of a list and returns an iterator
 * to that location.
 * @param: start - an iterator holding the location to start searching from
 * @param: length - the number of elements to check
 * @param: comparer - a comparing function which retruns true if the 1st
 * element is smaller than the 2nd
 */
	template<typename Compare>
	Iterator<T> findMin(Iterator<T> start, int length, const Compare& comparer) {
		T min = *start;
		Iterator<T> minIt = start;
		for (int i = 1; i < length; ++i) {
			++start;
			if (!comparer(min, *start)) {
				min = *start;
				minIt = start;
			}
		}
		return minIt;
	}
	// clears the list of all it's nodes but the dummy.
	void listClear() {
		int length(size);
		for (int i = 1; i <= length; ++i) {
			remove(begin());
		}
	}
	// makes "this" list be a copy of "list"
	void listCopy(List& list) {
		Iterator<T> originIterator = list.begin();
		while (originIterator != list.end()) {
			this->insert(*originIterator, this->end());
			++originIterator;
		}
	}

public:
	List() :
		size(0), head(new Node<T> ()) {
	}
	List(List& list) : size(0), head(new Node<T> ()) {
		listCopy(list);
	}
	~List() {
		listClear();
		delete head;	//remove the dummy
	}
	List<T>& operator=(const List& list) {
		if (this != &list) {
			listClear();
			listCopy(list);
		}
		return *this;
	}
	// returns the number of nodes in the list
	int getSize() const {
		return size;
	}
	/*Returns iterator to the beginning of the list. Iterator points to the
	 *first member list.If the list is empty, returned iterator end of the list.
	 */
	Iterator<T> begin() {
		return Iterator<T> (this, head);
	}
	/* Returns iterator to the end of the list. As mentioned, iterator pointing
	 * to any node not to the list itself.
	 */
	Iterator<T> end() {
		Iterator<T> newIterator = begin();
		for (int i = 0; i <= this->size; ++i) {
			++newIterator;
		}
		return newIterator;
	}
	/* Add a new node with the value of list data.If the iterator points to end
	 *  of the list, then the new element is inserted into the end of the list.
	 *	Otherwise, the new node will be inserted before the iterator pointing
	 *  to the node. If the iterator is of a different list, throw the
	 *  exception ListExceptions:: ElementNotFound.
	 */
	void insert(const T& data, Iterator<T> iterator) {
		this->compareLists(iterator.motherList);
		/*
		 * copy the current node, using the default copy c'tor
		 * make the current node point to that copy, and change the data
		 * in the current node
		 */
		iterator.current->next = new Node<T> (*(iterator.current));
		iterator.current->data = new T(data);
		++size;
	}
	/* Node removal from the list iterator pointing to it. If the list is empty,
	 * or the iterator points to the end of the list, throw the exception
	 * ListExceptions:: ElementNotFound, which appears in mtm.h.
	 * If the iterator is of a different list, throw the exception
	 * ListExceptions:: ElementNotFound.
	 */
	void remove(Iterator<T> iterator) {
		if ((this->size <= 0) || (iterator == this->end())) {
			throw ElementNotFound();
		}
		this->compareLists(iterator.motherList);

		if (this->begin() == iterator) {
			this->head = iterator.current->next;
		} else {
			Iterator<T> tempIterator = this->begin();
			Node<T>* prevNode = head;
			while (tempIterator != iterator) {
				prevNode = tempIterator.current;
				++tempIterator;
			}
			prevNode->next = iterator.current->next;
		}
		delete iterator.current;
		--size;
	}
	/* Find member list.If there is a part of a list that equals the condition
	 * function - Predicate dictates, should be returned iterator to him.
	 * If there are several such nodes, should be returned to the first one.
	 * If there is no such node, it will return iterator to the end of the list.
	 */
	template<typename Predicate>
	Iterator<T> find(const Predicate& predicate) {
		Iterator<T> newIterator = this->begin();
		while (newIterator != this->end()) {
			if (predicate(*newIterator)) {
				break;
			}
			++newIterator;
		}
		return newIterator;
	}
	/* sort the list so that every two follow elements sorted list, obj1 and
	 * obj2 (when obj1 first to obj2 in the list), comparer (obj1,obj2) == true
	 */
	template<typename Compare>
	void sort(const Compare& comparer) {
		int unchecked = this->size;
		while (unchecked > 0) {
			Iterator<T> minIt = this->findMin<Compare> (this->begin(), unchecked,
					comparer);
			T minVal = *minIt;
			this->remove(minIt);
			this->insert(minVal, this->end());
			--unchecked;
		}
	}
};
#endif /* LIST_H_ */
